#ifndef _BASIC_H_
#define _BASIC_H_

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INFTY   2147483647
//      
//      basic common functions
//
int     abs ( int x )
{
        return  x>0?x:-x;
}
int     min ( int x, int y )
{
        return  (x<y)?x:y;
}
int     max ( int x, int y )
{
        return  (x>y)?x:y;
}
//
//      some array functions
//
int     *new_array ( int size )
{
        int *array;
        if (!(array=(int*)calloc(size,sizeof(int))))
                exit (0);
        return  array;
}
float   *new_float_array ( int size )
{
        float   *array;
        if (!(array=(float*)calloc(size,sizeof(float))))
                exit (0);
        return  array;
}
void    assign_array ( int *array, int size, int val )
{
        for ( int i = 0; i < size; ++i )
                array[i] = val;
}
void    assign_float_array ( float *array, int size, float val )
{
        for ( int i = 0; i < size; ++i )
                array[i] = val;
}
int     contain_array ( int *array, int size, int val )
{
        for ( int i = 0; i < size; ++i )
                if ( array[i] == val )
                        return 1;
        return 0;
}
int     non_zero_array ( float  *array, int size )
{
        int     cnt = 0;
        for ( int i =0; i<size; i++ )
                if ( array[i] )
                        ++ cnt;
        return cnt;
}
void    swap ( int *array, int i, int j )
{
        int     tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
}
int     ext_max ( float *array, int size )
{
        float   max = 0;
        int     tmp = -1;
        for (int i=0; i<size; i++)
                if ( array[i]>max )
                {
                        max = array[i];
                        tmp = i;
                }
        return  tmp;
}
//
//      some linked list functions
//
int_LL  *new_int_LL ()
{
        int_LL  *node;
        if (!(node=(int_LL*)malloc(sizeof(int_LL))))
                exit (0);
        node->next = NULL;
        return node;
}
int     find_int_LL ( int edge_id, int_LL *linklist )
{
        int_LL  *node;
        for ( node = linklist; node->next; node=node->next )
                if ( node->next->num == edge_id )
                        return 1;
        return  0;
}
void    insert_int_LL ( int id, int_LL *linklist )
{
        if ( !find_int_LL ( id, linklist ) )
        {
                int_LL  *node = new_int_LL ();
                node->num = id;
                node->next = linklist->next;
                linklist->next = node;
        }
}
void    remove_int_LL ( int id, int_LL *linklist )
{
        if (find_int_LL ( id, linklist ))
        {
                int_LL  *node;
                for ( node = linklist; node->next; node=node->next )
                        if ( node->next->num == id )
                        {
                                node->next = node->next->next;
                                return;
                        }
        }
}
int     deQ_int_LL ( int_LL *linklist )
{
        int     k = linklist->next->num;
        linklist->next = linklist->next->next;
        return  k;
}
int     length_int_LL ( int_LL *linklist )
{
        int     cnt = 0;
        int_LL  *node;
        for ( node = linklist; node->next; node=node->next )
                cnt ++;
        return  cnt;
}
int     *int_LL_to_array ( int_LL *list )
{
        int     *array = (int*)calloc(length_int_LL(list), sizeof(int));
        int     i = 0;
        int_LL  *node;
        for ( node = list; node->next; node=node->next )
                array[i++] = node->next->num;
        return  array;
}
//
//      sorting algorithm functions
//
int     partition ( int *list, int left, int right, float *key )
{
        int     pivot = left;
        int     store_right = right;
        while ( pivot < store_right )
        {
                if ( key[list[pivot]] < key[list[pivot+1]] )
                {
                        swap ( list, pivot, pivot+1 );
                        ++ pivot;
                }
                else
                {
                        swap ( list, pivot+1, store_right );
                        -- store_right;
                }
        }
        return  pivot;
}
void    quicksort ( int *list, int left, int right, float *key )
{
        if ( left < right )
        {
                int     newpivot;
                newpivot = partition ( list, left, right, key );        // pick pivot as left-most element
                if ( left <= newpivot-1 )
                        quicksort ( list, left, newpivot-1, key );
                if ( newpivot+1 <= right )
                        quicksort ( list, newpivot+1, right, key );
        }
}
int     pre_sort ( int *list, int left, int right, float *key )
{
        int     pivot = left;
        int     store_right = right;
        while ( pivot < store_right )
        {
                if ( key[list[pivot]] )
                        ++ pivot;
                else
                {
                        swap ( list, pivot, store_right );
                        -- store_right;
                }
        }
        return  pivot;
}
int     *sort_array ( float *weight, int numNets )
{
        int     *sort = new_array ( numNets ); 
        for (int i=0; i < numNets; ++i)
                sort[i] = i;
        int     non_zero_pos = pre_sort ( sort, 0, numNets-1, weight );
        quicksort ( sort, 0, non_zero_pos, weight );
        return  sort;
}
void    reverse_array ( int *array, int size )
{
        for ( int i = 0; i < size/2; i ++ )
                swap ( array, i, size-1-i );
}
//
//      heap
//
int     pull_priority_queue ( int *heap, float *val )
{
        if ( heap[0] < 1 )
                return 0;
        int     min = heap[1];
        heap[1] = heap[heap[0]];
        -- heap[0];
        MIN_HEAPIFY ( heap, 1, val );
        return  min;
}
void    insert_priority_queue ( int k, int *heap, float *val )
{
        ++ heap[0];
        heap[heap[0]] = INFTY;
        HEAP_DECREASE_KEY ( heap, heap[0], k, val );
}
int     is_in_queue ( int k, int *heap )
{
        for ( int i = 1; i <= heap[0]; i++ )
                if ( heap[i] == k )
                        return  1;
        return  0;
}

#endif 
